#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


//
//void qsort(vector<int>& nums, int left, int right)
//{
//    if (left >= right) return;
//    int key = left;
//    while (left < right)
//    {
//        while (left < right && nums[right] >= nums[key])
//            right--;
//        while (left < right && nums[left] <= nums[key])
//            left++;
//        swap(nums[left], nums[right]);
//    }
//    swap(nums[left], nums[key]);
//
//    qsort(nums, 0, left - 1);
//    qsort(nums, left + 1, right);
//}


//void qsort(vector<int>& nums, int l, int r)
//{
//    if (left >= right) return;
//    int key = nums[l];
//    int left = l - 1, right = r + 1;
//    int i = l;
//    while (i < right)
//    {
//        if (nums[i] < key) swap(nums[i++], nums[++left]);
//        else if (nums[i] == key) i++;
//        else swap(nums[i], nums[--right]);
//    }
//    qsort(nums, l, left);
//    qsort(nums, right, r);
//}


//vector<int> sortArray(vector<int>& nums) {
//    int left = 0, right = nums.size() - 1;
//    qsort(nums, 0, right);
//    return nums;
//}


void qsort(vector<int>& nums, int l, int r)
{
    if (l >= r) return;
    int key = nums[l];
    int left = l - 1, right = r + 1, i = l;
    while (i < right)
    {
        if (nums[i] < key) swap(nums[i++], nums[++left]);
        else if (nums[i] == key) i++;
        else swap(nums[i], nums[--right]);
    }

    qsort(nums, l, left);
    qsort(nums, right, r);
}
vector<int> sortArray(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    srand(NULL);
    qsort(nums, left, right);
    return nums;
}


int main()
{
    vector<int> nums = { 5,2,3,1 };
    sortArray(nums);

    return 0;
}